﻿namespace Graph;

//求带权图单源最短路径
//思想：贪心法和迭代法
public class Dijkstra
{
    private IGraph G;
    private bool[] visited;

    private int s;
    private float [] dis;
    private int[] pre;

    // O（V^2）
    public Dijkstra(IGraph G, int s)
    {
        this.G = G;
        this.s = s;

        visited = new bool[G.V];
        dis = new float[G.V];
        pre = new int[G.V];
        for (int i = 0; i < G.V; i++)
        {
            dis[i] = float.PositiveInfinity;
            pre[i] = -1;
        }
        dis[s] = 0; //dis数组的初值即为初解

        while (true) 
        {
            //1. 找到当前没有访问的最短路点（当前点）。

            int cur = -1;
            float curdis = float.PositiveInfinity;

            for (int v = 0; v < G.V; v++)
            {
                if (!visited[v] && dis[v] < curdis)
                {
                    curdis = dis[v];
                    cur = v;
                }
            }

            if (cur == -1) //所有顶点全部被访问过，while迭代终止。此时，dis数组即为终解。
            {
                break;
            }

            //2. 当前点设为被访问过，以确定就是最终的最短路点，之后不再更新。

            visited[cur] = true; //当前一个子问题得到终解，下次迭代会根据已解好的问题去解下一子问题


            //3. 从当前点起跳，更新相邻点的路长。(BFS)

            foreach (int w in G.Adj(cur))
            {
                if (!visited[w])
                {
                    float d = ((AdjDictionary)G).GetWeight(cur, w);
                    if (dis[cur] + d < dis[w])
                    {
                        dis[w] = dis[cur] + d;
                        pre[w] = cur;
                    }
                }
            }//foreach迭代结束的dis数组即为当前解。
        }
    }

    public bool IsConnectedTo(int t)
    {
        return visited[t];
    }

    public float Dis(int t)
    {
        return dis[t];
    }

    public MyList<int> Path(int t)
    {
        MyList<int> res = new MyList<int>();
        if (!IsConnectedTo(t))
        {
            return res;      
        }

        int cur = t;
        while (cur!=s)
        {
            res.Add(cur);
            cur=pre[cur];
        }
        res.Add(cur);

        res.Reverse();

        return res;
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjDictionary("带权图最短路径/g.txt");
        int s=0;

        Dijkstra dijkstra = new(graph, s);

        for (int t = 0; t < graph.V; t++)
        {
            Console.WriteLine($"dijkstra:{s}->{t}: {dijkstra.Dis(t)} {dijkstra.Path(t)}");
        }        

        Console.Read();
    }
}
